#include"tree.h"
BTNode* BuyNode(int val)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}

	newnode->left = NULL;
	newnode->right = NULL;
	newnode->val = val;
}
BTNode* CreateTree()
{
	BTNode* n1 = BuyNode(1);
	BTNode* n2 = BuyNode(2);
	BTNode* n3 = BuyNode(3);
	BTNode* n4 = BuyNode(4);

	n1->left = n2;
	n2->left = n3;
	n1->right = n4;
}
bool IsSameTree(BTNode* p, BTNode* q)
{
	if (p == NULL && q == NULL)
		return true;
	if (p == NULL || q == NULL)
		return false;
	if (p->val != q->val)
		return false;
	return IsSameTree(p->left, q->left) &&
		IsSameTree(p->right, q->right);
}

void QuickSort2(int* a, int left, int right)
{
	if (left >= right)
		return;
	int key = left;
	int prev = left;
	int cur = left+1;
	while (cur <= right)
	{
		if (a[cur] < a[key])
		{
			prev++;
			Swap(&a[cur], &a[prev]);
			cur++;
		}
		else
		{
			cur++;
		}
	}
	Swap(&a[key], &a[cur]);
	key = prev;
}

void QuickSort2(int* a, int left, int right)
{
	if (left >= right)
		return;
	int key = left;
	int prev = left;
	int cur = left + 1;
	while (cur <= right)
	{
		if (a[cur] < a[key])
		{
			prev++;
			Swap(&a[cur], &a[prev]);
			cur++;
		}
		else
		{
			cur++;
		}
	}
}